/*
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
*/

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > res;
        if (k <= 0 || k > n) return res;
        vector<int> arrin, resone;
        for (int i=0; i<n; i++) arrin.push_back(i+1);
        do_combine(arrin, resone, res, 0, k);
        return res;
    }
private:
    void do_combine(vector<int> &arrin, vector<int> &resone, 
        vector<vector<int> > &res, int start, int k) 
    {
        int len = arrin.size();
        for (int i = start; i < len; i++) {
            resone.push_back(arrin[i]);
            if (resone.size() == k) res.push_back(resone);
            do_combine(arrin, resone, res, i+1, k);
            resone.pop_back();
        }
    }
};

/*
class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > res;
        if (k > n) return res;
        vector<int> arrin(n, 0);
        vector<int> item;
        for (int i=1; i<=n; i++) {arrin[i-1] = i;}
        for (int i=0; i<=n-k; i++) {
            item.push_back(arrin[i]);
            _combine(arrin, res, item, i+1, n, 1, k);
            item.pop_back();
        }
        return res;
    }
private:
    void _combine(vector<int> & array, vector<vector<int> > & res, vector<int> &item,
        int start, int end, int level, int target) {
        if (level++ == target) {
            // stop when collecting
            res.push_back(item);
            return;
        }
        for (int i = start; i < end; i++) {
            item.push_back(array[i]);
            _combine(array, res, item, i+1, end, level, target);
            item.pop_back();
        }
    }
};
*/
